/**
 * 101. 对称二叉树
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
  const stackLeft = [];
  const stackRight = [];
  let nodeLeft = root.left;
  let nodeRight = root.right;
  while ((stackLeft.length && stackRight.length) || nodeLeft || nodeRight) {
    while (nodeLeft && nodeRight) {
      if (nodeLeft.val !== nodeRight.val) return false;
      stackLeft.push(nodeLeft);
      nodeLeft = nodeLeft.left;
      stackRight.push(nodeRight);
      nodeRight = nodeRight.right;
    }
    if (nodeLeft || nodeRight) return false;
    nodeLeft = stackLeft.pop();
    nodeLeft = nodeLeft.right;
    nodeRight = stackRight.pop();
    nodeRight = nodeRight.left;
  }
  return true;
}

console.log(isSymmetric(createTreeNode([1, 2, 2, 3, 4, 4, 3])) === true);
console.log(isSymmetric(createTreeNode([1, 2, 2, null, 3, null, 3])) === false);
